//*************************************************
//Program #4       Optimal.cpp
//*************************************************
//Names: Stephen Durfrey,  Andrew Brock
//Due: April 23, 2010
//Operating Systems
//Related Files:  Optimal.h
// Optimal PRA: Guaruntees the lowest possible page fault rate
//  for a fixed number of frames.


#include "Optimal.h"
#include <algorithm>
#include <vector>
#include <string>
#include <stdlib.h>

using namespace std;

//Default constructor
Optimal::Optimal()
{
}
//*************************************************
//Optimal::init - initializes the varibles based on the variables
// passed into the program.
//*************************************************
void Optimal::init(int frames, vector<int> ref_str)
{
	num_frames = frames;
	ref_string = ref_str;
	num_faults = 0;
	ref_page = ref_string.begin();
}
//*************************************************
//Optimal::checkFrame - checks to see if the value "check"
// is in the frames.  If it is its location is passed back
// otherwise check == frames.end()
//*************************************************
vector<int>::iterator Optimal::searchFrames(vector<int>::iterator value, vector<int>::iterator &replace)
{
	vector<int>::iterator begin, end, max, position;
    	bool found = false;

	end = frames.end();
	max = value;
    
	

	for(begin = frames.begin(); begin != end && !found; begin++)
	{
		position = find(ref_page, ref_string.end(), *begin);

		if(position == ref_string.end())
		{		
			max = position;
			replace = begin;
			found = true;
		}
		else if(position > max)
			max = position;
	}

	return max;

}
//*************************************************
//Optimal::checkFrame - checks to see if the value "s_val" is inside
// of framesList.  If it isn't inFrame is false.
//*************************************************
vector<int>::iterator Optimal::findFrame(vector<int>::iterator max)
{
	bool found = false;
	vector<int>::iterator value, begin, end;

	value = end = frames.end();

	for(begin = frames.begin(); begin != end && !found; begin++)
	{
		if(*begin == *max)
		{
			value = begin;
			found = true;
		}
	}

	return value;

}
//*************************************************
//Optimal::findPage - this is where the loop is that the Optimal
// page replacement algorithm is tested.
//*************************************************
void Optimal::findPage()
{
	vector<int>::iterator max, position, begin, end, replace;
	

	end = ref_string.end();
	

	for(begin = ref_string.begin(); begin != end; begin++, ref_page++)
	{//BEGIN FOR
		replace = frames.begin();

		if(frames.size() != num_frames)
		{//BEGIN IF
			position = findFrame(begin);
			if(position == frames.end())
			{
				//Frames are empty
				frames.push_back(*begin);
				num_faults++;
			}
		}//END IF
		else
		{//BEGIN ELSE
			//Checks to see if value is in the frames.
			position = findFrame(begin);
			if(position == frames.end())
			{
			  max = searchFrames(begin, replace);

			  if(max == end)
			  {
				  //Didn't Find another instance of the current *frame.
				  *replace = *ref_page;
				  num_faults++;
			  }
			  else if(max != end)
			  {
				  //found an instance of the current *frame
				  position = findFrame(max);
				  *position = *ref_page;
				  num_faults++;
			  }
			}
			else
			{
				//its in the Frames
				continue;
			}
		}//END ELSE
	}//END FOR
}
//*************************************************
//Optimal::run - executes the algorithm and then outputs
// the results of values num_frames and num_faults
//*************************************************
void Optimal::run()
{
	char value[50];
	string value_param;

	findPage();

	sprintf(value, "%d , %d", num_frames, num_faults);

	value_param = (string)value;
	addCsvString("Optimal.txt", value_param );
}

